﻿//2563. 统计公平数对的数目
//给你一个下标从 0 开始、长度为 n 的整数数组 nums ，和两个整数 lower 和 upper ，返回 公平数对的数目 。
//如果(i, j) 数对满足以下情况，则认为它是一个 公平数对 ：
//0 <= i < j < n，且 lower <= nums[i] + nums[j] <= upper


class Solution {
public:
    long long countFairPairs(vector<int>& nums, int lower, int upper)
    {
        int n = nums.size();
        long long ans = 0;
        sort(nums.begin(), nums.end());
        int left = n - 1, right = n - 1;
        for (int i = 0; i < n; i++)
        {
            //下界
            int low = lower - nums[i];
            //上界
            int up = upper - nums[i];

            while (right >= 0 && nums[right] > up)
            {
                right--;
            }

            while (left >= 0 && nums[left] >= low)
            {
                left--;
            }

            if (right > i)
            {
                if (left >= i)
                {
                    ans += right - left;
                }
                else
                {
                    ans += right - i;
                }
            }
        }
        return ans;
    }
};